\section{Preliminary Knowledge}\label{Preliminary Knowledge}
%\subsection{System Model and Problem Statement}
%This paper considers a large-scale RFID system that contains tens of thousands items that are attached with RFID tags, each of them has a unique 96-bit ID. The RFID readers monitor or identify the items by communicating with RFID tags that are attached to the items. In practice, the items confined within a warehouse (or store) typically belong to different categories, e.g., different brands of clothes in a large clothing store, different titles of books in a book store, etc \cite{infocomXieLei}. To support category specification, each tag ID contains two fields: a category ID, which specifies the category information of the tagged item; and a member ID, which is used to identify the specific item of a category \cite{ShigangInfocomMultiGroup}. %Clearly, the tags that are attached to the same category of items should have the same category ID. In contrary, the tags that are attached to different categories of items should have different category IDs.

%\begin{figure}[!htpb]
%%\setlength{\belowcaptionskip}{-0.1cm}
%\centerline{\includegraphics[scale=0.4]{Fig/problemModel}}
%\caption{Tag population changes in multi-category RFID systems.}
%\label{problemModel}
%\end{figure}

%We assume that the set of distinct category IDs of the tags in the system, denoted as $C=\{C_1,C_2,..., C_\eta\}$, is known in prior, where $\eta$ is the number of tag categories

%Supposing there are $\lambda$ tag categories in the system. We denote the category ID of the $i^{th}$ category as $C_i$. Further, we use $S_i$ to denote the tag set of category $C_i$, $i\in[1,\lambda]$. And $n_i$ is the cardinality (i.e., number) of category $C_i$. In this paper, we study the problem of multi-category RFID cardinality estimation. This problem is formally defined as follows: \emph{given a confidence interval $\alpha\in (0,1]$, and (2) a required reliability $\beta\in [0,1)$, our goal is to use one or more readers to estimate the cardinality of each category $i$, denoted as $\hat{n_i}$, so that $P\{|\hat{n_i}-n_i|\leq n\alpha\}\geq\beta$, $i\in[1,\lambda]$.}

\subsection{Manchester Coding}
%\begin{figure}
%\centering
%\epsfig{file=Fig/ManchesterCode.eps}
%\caption{Manchester Coding.}\label{ManchesterCode}
%\end{figure}
Before sending data, each RFID tag needs to encode the backscattered data first. %FM0 coding and Miller coding are supported in EPC-C1G2 standard \cite{epcglobal2004radio}. However, these two codes cannot be used to detect the bit collision \cite{XieLeiIC3NRuleChecking}.
In this paper, we use the Manchester coding, supported by the well-known ISO 18000-6 \cite{ISO18000} RFID standard, to detect the bit-level collisions \cite{YuanHsinTIndusI} \cite{YuanChengTMC}. Specifically, as illustrated in Fig.\ref{ManchesterCode}, `1' is coded as a falling edge, while `0' is coded as a rising edge. The data transmission in a slot is well synchronized by the beacon signal from the reader \cite{XieLeiIC3NRuleChecking}. If all tags transmit `0' (or `1') concurrently, the reader could successfully recover the bit as `0' (or `1'). In contrary, if some tags transmit `0' while the others transmit `1', the reader will detect a bit collision `x'.
\begin{figure}[htb]
\centerline{\includegraphics[scale=0.35]{Fig/ManchesterCode}}
\vspace{-0.1in}
\caption{Manchester Coding.}
\label{ManchesterCode}
\end{figure}
\vspace{-0.2in}

\subsection{MAC Layer Communication}
The commercial RFID standard adopts the Framed Slotted Aloha protocol \cite{lee2005enhanced} as the MAC layer communication mechanism, which is described as follows. The RFID reader initializes a slotted time frame by broadcasting a binary request $\langle \delta,f \rangle$, where $\delta$ is a random seed and $f$ is the frame size (i.e., the number of slots in the forthcoming frame). Each tag randomly determines a slot in the frame to reply its ID or other stored information (such as category ID, manufacturer, and price) to the reader. Specifically, using the received parameters $\langle \delta,f \rangle$, each tag initializes its slot counter $sc$ by calculating $sc=H(ID,\delta)\mod f$ and the hashing result follows a uniform distribution within $[0,f-1]$. The reader broadcasts \emph{QueryRep} command at the end of each slot, thereby informing a tag to decrement its slot counter $sc$ by 1. In a slot, a tag responds to the reader once its slot counter $sc$ becomes 0. The duration of a slot for transmitting $\gamma$-bit data, denoted as $t_{\gamma}$, is $\tau_w+\gamma\times\tau_b$, where $\tau_w$ is the waiting time and $\tau_b$ is the time for transmitting 1-bit data. In this paper, $\tau_w$ and $\tau_b$ are configured to 302us and 18.8us \cite{XieLeiIC3NRuleChecking} \cite{QiaoMobihoc11}, respectively. The main notations used in this paper are summarized in~Table~\ref{Notations1}.
%
%
%\begin{table}
%\centering
%\caption{Frequency of Special Characters}
%\begin{tabular}{|c|c|l|} \hline
%Non-English or Math&Frequency&Comments\\ \hline
%\O & 1 in 1,000& For Swedish names\\ \hline
%$\pi$ & 1 in 5& Common in math\\ \hline
%\$ & 4 in 5 & Used in business\\ \hline
%$\Psi^2_1$ & 1 in 40,000& Unexplained usage\\
%\hline\end{tabular}
%\end{table}
\vspace{-0.2in}
\begin{table}[htb] \caption{Symbols used in the paper} \label{Notations1}
\scriptsize
  \begin{center}
    \begin{tabular}{|p{1.5cm}<{\centering}|p{6cm}|m|l|}
       \hline
       \textbf{Notations} & \textbf{Descriptions}\\
       \hline
       $\lambda$ & \# of tag categories under estimation.\\
       \hline
       $C_i$ & category ID, $i\in[1,\lambda]$.\\
       \hline
       $S_i$   & tag set of category $C_i$.\\
       \hline
       $n_i$ & tag cardinality of category $C_i$. \\
       \hline
       $\alpha$ & required confidence interval.\\
       \hline
       $\beta$ & required reliability.\\
       \hline
       $\hat{n_i}$ & estimate of $n_i$.\\
       \hline
       $\delta$   & random number.\\
       \hline
       $f$   & initial frame size.\\
       \hline
       $f'$  & observed frame size.\\
       \hline
       $H(\cdot)$  & uniform hash function.\\
       \hline
       $\tau_w$ & waiting time in a slot.\\
       \hline
       $\tau_b$ & time for transmitting 1-bit data from tag to reader.\\
       \hline
       $t_{\gamma}$ & duration of slot that transmits $\gamma$-bit data. $t_{\gamma}=\tau_w+\gamma \tau_b$.\\
       \hline
       $F_{i}[..]$ & logical frame for category $C_i$.\\
       \hline
       $p_{i,e}$ & probability that a slot in $F_{i}[..]$ is empty.\\
       \hline
       $N_{i,e}$ & \# of empty slots in $F_{i}[..]$.\\
       \hline
       $\hat{n_{i,j}}$ & estimate for category $C_i$ derived from the $j^{th}$ round of estimation.\\
       \hline
       $A_k(\hat{n_i})$ & averaged result of $k$ rounds of estimation for category $C_i$. $A_k(\hat{n_i})=\frac{1}{k}\sum^k_{j=1}\hat{n_{i,j}}$\\
       \hline
    \end{tabular}
  \end{center}
\end{table}
\vspace{-0.2in}